package com.example.topologicalsorting43;

import java.util.LinkedList;

/**
 * 深度优先遍历（DFS）
 * @auther lijiewei
 * @date 2022/6/23 13:31
 */
public class DFS {

    public void topoSortByDFS(Graph graph) {
        //正向邻接表，边s->t表示，t依赖于s, s先于t
        LinkedList<Integer>[] adj = graph.getAdj();
        int v = graph.getV();

        //先构建逆邻接表，边s->t表示，s依赖于t, t先于s
        LinkedList<Integer> inverseAdj[] = new LinkedList[v];
        //初始化链表
        for (int s = 0; s < v; s++) {
            inverseAdj[s] = new LinkedList<>();
        }
        //通过邻接表生成逆邻接表
        for (int s = 0; s < v; s++) {
            for (int i = 0; i < adj[s].size(); i++) {
                Integer t = adj[s].get(i); //s->t
                inverseAdj[t].add(s); //t->s
            }
        }

        //记录顶点是否被访问
        boolean[] visited = new boolean[v];
        //深度优先遍历
        for (int s = 0; s < v; s++) {
            if (visited[s] == false) {
                visited[s] = true;
                dfs(s, inverseAdj, visited);
            }
        }
    }

    private void dfs(int s, LinkedList<Integer>[] inverseAdj, boolean[] visited) {
        for (int i = 0; i < inverseAdj[s].size(); i++) {
            Integer t = inverseAdj[s].get(i);
            if (visited[t]) {
                continue;
            }
            visited[t] = true;
            dfs(t, inverseAdj, visited);
        }
        //先把s顶点可达的所有顶点打印后，再打印s顶点
        System.out.print("->"+s);
    }
}
